import java.util.Scanner;

public class KnapsackBacktrack  {
    static int[] v = {2, 9, 9, 10, 24}; // 固定价值
    static int[] w = {3, 4, 4, 5, 10};  // 固定体积
    static int n;      // 用户输入的商品数量
    static int G;      // 用户输入的背包容量
    static int max = 0;
    static int[] path;
    static int[] best;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("请输入要考虑的商品数量n：");
        n = sc.nextInt();
        if (n > 5) {
            System.out.println("最多只能输入5个商品，程序退出。");
            return;
        }

        System.out.print("请输入背包容量G：");
        G = sc.nextInt();

        path = new int[n];
        best = new int[n];

        dfs(0, 0, 0);

        System.out.println("\n最大价值：" + max);
        System.out.print("选择的商品编号（从0开始）：");
        for (int i = 0; i < n; i++) {
            if (best[i] == 1) System.out.print(i + " ");
        }
    }

    static void dfs(int i, int cw, int cv) {
        if (i == n) {
            if (cv > max) {
                max = cv;
                System.arraycopy(path, 0, best, 0, n);
            }
            return;
        }

        // 选商品i
        if (cw + w[i] <= G) {
            path[i] = 1;
            System.out.println("选中商品" + i + "，当前体积：" + (cw + w[i]) + "，当前价值：" + (cv + v[i]));
            dfs(i + 1, cw + w[i], cv + v[i]);
        }

        // 不选商品i
        path[i] = 0;
        System.out.println("不选商品" + i + "，当前体积：" + cw + "，当前价值：" + cv);
        dfs(i + 1, cw, cv);
    }
}
